class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x;
        while (l < r) {
            long long int mid = l + (r - l) / 2;
            if (mid* mid < x) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }

        return r * r > x ? r - 1 : r;
    }
};